package com.cdream.basic.algorithm.leetcode.dp;

public class Question377 {
    private int count = 0;

    public static void main(String[] args) {
        new Question377().combinationSum4(new int[]{1, 2, 3, 4, 5}, 4);
    }

    public int combinationSum4v2(int[] nums, int target) {
        // 从nums中任意取数，和为target的数量
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int j = 1; j <= target; j++) {
            for (int num : nums) {
                if (num <= j) {
                    dp[j] += dp[j - num];
                }
            }
        }
        return dp[target];
    }


    public int combinationSum4(int[] nums, int target) {
        // 任意取i个元素和为target的方案
        // 因为nums中的元素都是正整数，所以最多可以取target个元素
        int[][] dp = new int[target + 1][target + 1];
        dp[0][0] = 1;
        // 取0~target个元素
        int count = 0;
        for (int i = 1; i <= target; i++) {
            // 数组和为target
            for (int j = 0; j <= target; j++) {
                // 选数最后一个元素
                for (int num : nums) {
                    if (num <= j) {
                        dp[i][j] += dp[i - 1][j - num];
                    }
                }

            }
            count += dp[i][target];
        }
        return count;
    }

    private void dfs(int[] nums, int target) {
        if (target == 0) {
            count++;
            return;
        }
        if (target < 0) {
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            dfs(nums, target - nums[i]);
        }
    }
}
